\begin{proof}[\textbf{Solution~\ref{ex:number_theory:powermod_Fermat_little_theorem}}]
The function {\tt a.powermod(e,p)} computes the result of $a^e \bmod p$ 
by doing an optimal number of squarings and multiplications, and reducing 
the intermediate results.  The size of the expanded result $a^e$ for 
large $e$, such as for $e = p-1 = 2^{31}-2$, would overflow the internal 
storage capacity of a computer, so it would be unwise to attempt to 
structure the algorithm as $a \mapsto a^e$ then to reduce modulo $p$. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:number_theory:use_powermod_verify_Fermat_little_theorem}}]
For primes $p = 2^{31}-1$ and $q = (2^{61}-1)/3$, we compute for 
$a = 2$ the power ${\tt 2.powermod}(p-1,pq) = 103161671333561841019606358$.
If we reduce modulo~$q$, then result is $624499148328708779$ --- 
pretty much a random number of size $q$.  On the other hand, if we 
reduce modulo~$p$, the result is $1$.  This follows from Fermat's 
little theorem, since ${\tt 2.powermod}(p-1,pq) \bmod p$ is equal to 
the result ${\tt 2.powermod}(p-1,p)$.
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:number_theory:powermod_polynomial_analogue_Fermat_little_theorem}}]
For the polynomial $g(x) = x^{17} + x^5 + 1$, we should use exponent 
$e = 2^{17}-1$, which we note is prime.  We verify that each of the 
results $x.{\tt powermod}(e,g)$ and $(x^2+x+1){\tt powermod}(e,g)$ is $1$.
Since $e$ is prime, this proves that $g(x)$ is not only irreducible,
but also primitive. 
\end{proof}

\begin{proof}[\textbf{Solution~\ref{ex:number_theory:verify_polynomial_analogue_Fermat_little_theorem}}]
With $g(x)$ as above and $h(x) = x^{17} + x^{15} + x^{10} + x^5 + 1$, 
the results {\tt x.powermod(e,gh).mod(g)} equals $1$ holds as expected, 
exactly as in the previous exercise.  In this case, if $h(x)$ is also 
irreducible, then the result: 
$$
x.{\rm powermod}(e,gh) \bmod h = 
x^{16} + x^{15} + x^{14} + x^{11} + x^{10} + x^8 + x^6 + x^3 + 1
$$
would also have been $1$.  The fact that this result does not give 
$1$ is a consequence of the reducibility of $h$:
$$
h = (x^3 + x^2 + 1)
     (x^{14} + x^{13} + x^{11} + x^8 + x^5 + x^4 + x^3 + x^2 + 1).
$$
\end{proof}
